package LeetCode;

import com.company.Tree.Tree;

import java.awt.print.Pageable;

/**
 * @author VX5
 * @Title: MJC
 * @ProjectName interview
 * @Description: TODO
 * @date ${DAT}17:31
 */
public class LeetCode450 {
    public static class TreeNode {
      int val;
      TreeNode left;
      TreeNode right;
      TreeNode(int x) { val = x; }
   }
    // 要删除节点的三种情况
    // 1、要删除的节点为叶子节点，可以直接删除。

    // 2、要删除的几点不是叶子节点且拥有右节点，则该节点可以由该节点的后继节点进行替代，该后继节点位于右子树中较低的位置。然后可以从后继节点的位置递归向下操作以删除后继节点。
    // 3、要删除的节点不是叶子节点，且没有右节点但是有左节点。这意味着它的后继节点在它的上面，但是我们并不想返回。我们可以使用它的前驱节点进行替代，然后再递归的向下删除前驱节点。

    /*
    如果 key > root.val，说明要删除的节点在右子树，root.right = deleteNode(root.right, key)。
    如果 key < root.val，说明要删除的节点在左子树，root.left = deleteNode(root.left, key)。
    如果 key == root.val，则该节点就是我们要删除的节点，则：
    如果该节点是叶子节点，则直接删除它：root = null。
    如果该节点不是叶子节点且有右节点，则用它的后继节点的值替代 root.val = successor.val，然后删除后继节点。
    如果该节点不是叶子节点且只有左节点，则用它的前驱节点的值替代 root.val = predecessor.val，然后删除前驱节点。

    */



//    public TreeNode deleteNode(TreeNode root, int key) {
//        if (root == null){
//            return root;
//        }
//        TreeNode node = preSearch(root,key);
//        TreeNode parent = node;
//        while (node.left != null){
//            node.val = node.left.val;
//            parent = node;
//            node = node.left;
//        }
//        while (node.right != null){
//            node.val = node.right.val;
//            parent  = node;
//            node = node.right;
//        }
//        parent.val = node.val;
//        node = null;
//        return root;
//    }
//
//    public TreeNode preSearch(TreeNode root,int val){
//        if (root == null){
//            return null;
//        }
//        if (root.val != val){
//            if (root.val > val){
//                return preSearch(root.left,val);
//            }else {
//                return preSearch(root.right,val);
//            }
//        }else {
//            return root;
//        }
//    }

//    public TreeNode deleteNode(TreeNode root, int key) {
//        if (root == null){
//            return null;
//        }
//        if (root.val < key){
//            root.right = deleteNode(root.right,key);
//        }else if (root.val > key){
//            root.left = deleteNode(root.left,key);
//        }// 上面都是为了直接找到对应的节点
//        else if (root.left != null && root.right != null){// 找到目标结点，下面进行一个交换
//            if (root.right.left == null){
//                root.val = root.right.val;
//                root.right = root.right.right;
//            }else {
//                TreeNode min = root.right;
//                TreeNode minParent = root;
//                while (min.left != null){
//                    minParent = min;
//                    min = min.left;
//                }
//                root.val = min.val;
//                minParent.left = min.right;
//            }
//        }else {
//            root = root.left != null ? root.left : root.right;
//
//        }
//        return root;
//    }

    /*
    One step right and then always left
    */
    public int successor(TreeNode root) {
        root = root.right;
        while (root.left != null) root = root.left;
        return root.val;
    }

    /*
    One step left and then always right
    */
    public int predecessor(TreeNode root) {
        root = root.left;
        while (root.right != null) root = root.right;
        return root.val;
    }

    public TreeNode deleteNode(TreeNode root, int key) {
        if (root == null) return null;// 查无此点

        // delete from the right subtree
        if (key > root.val) root.right = deleteNode(root.right, key);
            // delete from the left subtree
        else if (key < root.val) root.left = deleteNode(root.left, key);
            // delete the current node
        else {
            // the node is a leaf 如果这是叶子结点
            if (root.left == null && root.right == null) root = null;
                // the node is not a leaf and has a right child
            // 这个节点不是叶子节点并且有一个右子节点
            else if (root.right != null) {
                root.val = successor(root);
                root.right = deleteNode(root.right, root.val);
            }
            // the node is not a leaf, has no right child, and has a left child
            // 这个节点不是叶子节点并且有一个左子节点
            else {
                root.val = predecessor(root);
                root.left = deleteNode(root.left, root.val);
            }
        }
        return root;
    }


    public static void main(String[] args) {
        TreeNode root = new TreeNode(5);
        root.left = new TreeNode(3);
        root.right = new TreeNode(6);
        root.left.left = new TreeNode(2);
        root.left.right = new TreeNode(4);
        root.right.right = new TreeNode(7);
        new LeetCode450().deleteNode(root,3);
    }
    public TreeNode deleteNode2(TreeNode root, int key) {
        if (root == null){
            return root;
        }
        // 通过递归的方式要先找到要删除的节点
        if (key > root.val){
            root.right = deleteNode2(root.right,key);
        }else if (key < root.val){
            root.left = deleteNode2(root.left,key);
        }else { // 找到该节点
            // 如果左子树为空那么直接返回右子树就行了
            if (root.left == null){
                return root.right;
            }
            // 如果右子树为空，我们只需要返回左子树即可
            if (root.right == null){
                return root.left;
            }
            // 如果两个节点都不为空，可以找左子树的最大值
            // 也可以找右子树的最小值替换

            // 使用右子树的最小值替换
            // TreeNode minNode = findMin(root.right);
            // root.val = minNode.val;
            // root.right = deleteNode2(root.right,root.val);// 因为此时已经将最小值替换过来了 剩下的还需要把原来的最小值删除掉

            // 使用左子树的最大值替换
            TreeNode maxNode = findMax(root.left);
            root.val = maxNode.val;
            root.left = deleteNode2(root.left,root.val);
        }
        return root;
    }

    private TreeNode findMax(TreeNode left) {
        while (left.right != null){
            left = left.right;
        }
        return left;
    }

    private TreeNode findMin(TreeNode right) {
        while (right.left != null){
            right = right.left;
        }
        return right;
    }

}
